package 归并排序;

import java.util.Arrays;

public class MergeSortNoRec {
    public static int[] mergeSort(int[] arr){
        int n =arr.length;
        //字数组的大小分别为1、2、4.....
        for (int i = 1;i<n;i+=i){
            //对数组进行划分
            int left = 0;
            int mid = left +i -1;
            int right = mid + i;
            //进行合并
            while (right<n){
                merge(arr,left,mid,right);
                left = right+1;
                mid = left +i -1;
                right = mid + i;
            }
            if (left<n&&mid<n){
                merge(arr,left,mid,n-1);
            }
        }
        return arr;
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        //先用一个临时数组将他们合并汇总起来
        int[] temp = new int[right-left+1];
        //记录第一个数组中需要遍历的下标
        int i = left;
        //纪录第二个数组中需要遍历的下标
        int j = mid+1;
        //用于纪录在临时数组中存放的下标
        int index = 0;
        //遍历两个数组取出小的数字放入临时数组
        while (i<=mid&&j<=right){
            //第一个数组的数字更小
            if (arr[i]<=arr[j]){
                //把小的数字放到临时数组
                temp[index] = arr[i];
                //第一组下标相后移动
                i++;
            }else {
                temp[index] = arr[j];
                j++;
            }
            index++;
        }
        //处理多余的数据
        while (j<=right){
            temp[index] = arr[j];
            j++;
            index++;
        }
        while (i<=mid){
            temp[index] = arr[i];
            i++;
            index++;
        }
        //把临时数组中的数据重新存入原数组
        for (int k = 0; k < temp.length; k++) {
            arr[k+left] = temp[k];
        }
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 5, 77, 3, 14, 82, 2, 4};
        System.out.println(Arrays.toString(mergeSort(arr)));
    }
}
